package com.haidechizi.tree;

import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * @author: wangdejun
 * @create: 2020-03-14 15:24
 **/
public class HuffmanTree {

    public static TreeNode createHuffmanTree(int[] arr) {
        List<TreeNode> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(new TreeNode(arr[i]));
        }
        // 当集合中的元素大于而时，可以创建一个树
        while (list.size() > 1) {
            Collections.sort(list);
            TreeNode first = list.get(0);
            TreeNode second = list.get(1);
            TreeNode newNode = new TreeNode(first.getValue() + second.getValue());

            newNode.setLeft(first);
            newNode.setRight(second);
            list.remove(first);
            list.remove(second);
            list.add(newNode);
        }
        return list.get(0);
    }
}
